package lc_1130_叶值的最小代价生成树;

public class Solution {

	public int mctFromLeafValues(int[] arr) {
		int n = arr.length;
		int[][] mxs = new int[n][n];
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			mxs[i][i] = arr[i];
			for (int j = i - 1; j >= 0; j--) {
				mxs[j][i] = Math.max(mxs[j + 1][i], arr[j]);
				dp[j][i] = Integer.MAX_VALUE;
				for (int k = j; k < i; k++) {
					dp[j][i] = Math.min(dp[j][i], dp[j][k] + dp[k + 1][i] + mxs[j][k] * mxs[k + 1][i]);
				}
			}
		}
		return dp[0][n - 1];
	}

	public int mctFromLeafValues1(int[] arr) {
		int n = arr.length;
		int[][] mxs = new int[n][n];
		for (int i = 0; i < n; i++) {
			mxs[i][i] = arr[i];
			for (int j = i - 1; j >= 0; j--) {
				mxs[j][i] = Math.max(mxs[j + 1][i], arr[j]);
			}
		}
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = i - 1; j >= 0; j--) {
				dp[j][i] = Integer.MAX_VALUE;
				for (int k = j; k < i; k++) {
					dp[j][i] = Math.min(dp[j][i], dp[j][k] + dp[k + 1][i] + mxs[j][k] * mxs[k + 1][i]);
				}
			}
		}
		return dp[0][n - 1];
	}

	public static void main(String[] args) {

	}
}